package pratice.leetcode;

import org.junit.Test;

import java.util.Stack;

/**
 * @author 吴宇亮 on 2019/5/6 0006 下午 1:04
 */
public class Pratice234 {

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    @Test
    public boolean isPalindrome(ListNode head) {
        if(null == head) return true;

        //获取链表的长度
        int length = 0;
        ListNode node = head;
        if(null == head.next){
            length = 1;
        }else{
            do{
                length++;
            }while(null != (node = node.next));
        }

        Stack<Integer> stack = new Stack<>();
        //如果ListNode的长度为单数
        if(1 == length % 2){
            //入栈
            for(int i = 0, j = length / 2; i < j; i++){
                stack.push(head.val);
                head = head.next;
            }

            head = head.next;

            //出栈
            for(int i = length / 2 + 1, j = length; i < j; i++){
                if(head.val != stack.pop()){
                    return false;
                }
                head = head.next;
            }
        //如果ListNode的长度为双数
        }else{
            //入栈
            for(int i = 0, j = length / 2; i < j; i++){
                stack.push(head.val);
                head = head.next;
            }
            //出栈
            for(int i = length / 2 + 1, j = length; i <= j; i++){
                if(head.val != stack.pop()){
                    return false;
                }
                head = head.next;
            }
        }

        return true;
    }
}
